home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / TPTUTR~1.ZIP / PASCAL16.TXT < prev    next >
Text File  |  1996-03-21  |  5KB  |  173 lines

  1.                        Turbo Pascal for DOS Tutorial
  2.                             by Glenn Grotzinger
  3.                       Part 16: Searching an Array
  4.                 copyright(c) 1995-96 by Glenn Grotzinger
  5.  
  6. There was no defined problem in part 15, so we will start.
  7.  
  8. Sequential Array Search
  9. =======================
  10. This method for searching arrays for items is much like the bubblesort
  11. is for sorting arrays.  It works well for small arrays, but for larger
  12. arrays, it is very inefficient, if we are merely interested in the
  13. existence of an item in the array.  Basically, it's a very simple
  14. proposition to set up a sequential array search.
  15.  
  16. program example_of_sequential_search;
  17.  
  18.   var
  19.     a: array[1..15] of integer;
  20.     i, number: integer;
  21.     found: boolean;
  22.  
  23.   begin
  24.     randomize;
  25.     found := false;
  26.  
  27.     write('The array is: ');
  28.     for i := 1 to 15 do
  29.       begin
  30.         a[i] := random(10) + 1;
  31.         write(a[i], ' ');
  32.       end;
  33.     writeln;
  34.  
  35.     writeln('Enter a number, and we shall see if it is in the array');
  36.     readln(number);
  37.  
  38.     i := 1;
  39.     while i <= 15 do
  40.       begin
  41.         if a[i] = number then
  42.           begin
  43.             writeln(number, ' was found at position ', i);
  44.             { i := 15; can be done to break the loop on the first
  45.               encounter of the one if we are interested in just
  46.               whether the number exists in the array }
  47.             found := true;
  48.           end;
  49.         inc(i);
  50.       end;
  51.     if not found then
  52.       writeln(number, ' was not found in the array.');
  53.   end.
  54.  
  55. Binary Search
  56. =============
  57. The other type of algorithm we will discuss is the binary search.  It is
  58. to searching an array what the quicksort is to sorting an array.  Basically,
  59. what it will do is keep halfing the array...
  60.  
  61. This method of array search has a prerequisite of having the data sorted.
  62. Basically, we probably would want to sort data anyway to make it in
  63. a readily presentable format for the user, so this doesn't necessarily
  64. matter  (searches and sorts are products of data processing programs
  65. normally, anyway).
  66.  
  67. program example_of_binary_search;
  68.  
  69.   const
  70.     first = 1;
  71.     last = 15;
  72.   var
  73.     a: array[first..last] of integer;
  74.     i, number: integer;
  75.     found: boolean;
  76.     location: integer;
  77.  
  78.   procedure bsearch(var number, location: integer;
  79.                       lowend, highend: integer; var found: boolean);
  80.     var
  81.       midpoint: integer;
  82.     begin
  83.       if lowend > highend then
  84.         found := false
  85.       else
  86.         begin
  87.           midpoint := (lowend + highend) div 2;
  88.           if number = a[midpoint] then
  89.             begin
  90.               found := true;
  91.               location := midpoint;
  92.             end
  93.           else if number < a[midpoint] then
  94.             bsearch(number, location, lowend, midpoint-1, found)
  95.           else if number > a[midpoint] then
  96.             bsearch(number, location, midpoint+1, highend, found);
  97.         end;
  98.     end;
  99.  
  100.   begin
  101.     randomize;
  102.     found := false;
  103.  
  104.     write('The array is: ');
  105.     for i := 1 to 15 do
  106.       begin
  107.         { to insure we have sorted data }
  108.         a[i] := 3*i;
  109.         write(a[i], ' ');
  110.       end;
  111.     writeln;
  112.  
  113.     writeln('Enter a number, and we shall see if it is in the array');
  114.     readln(number);
  115.  
  116.     bsearch(number, location, first, last, found);
  117.  
  118.     if found then
  119.       writeln(number, ' was found at position ', location)
  120.     else
  121.       writeln(number, ' was not found. ');
  122.  
  123. end.
  124.  
  125. As you may be able to pick out of this, it is possible to write an iterative
  126. version of the bsearch procedure.  With sorting the array, though, this one
  127. is a little better than simply going through the array one by one, but it
  128. still has it's drawback of having to actually sort the information.
  129.  
  130. Another method available for use, which we will not discuss here is called
  131. hashing, which is a very complex matter.
  132.  
  133. What should you use?  The serial search I described originally could be
  134. very good, for a limited number of searches on a small array size.
  135.  
  136. If it's not good to do the serial search, and you needed to sort the data
  137. anyway, the binary search is best.
  138.  
  139. Another method you may see as possible to use will be covered later, called
  140. the binary search tree.  The cost in that approach will be basically building
  141. the tree initially, then traversing it.  The tree is built based on specific
  142. rules, which we can exploit to cause a search.
  143.  
  144. Practice Programming Problem #16
  145. ================================
  146. Randomly generate 1000 numbers from 1-10000 into an array.
  147. Then generate another 500 numbers from 1-10000.
  148. If there is a number from the second set of numbers that happens
  149. to be in the first set of numbers, write out to the file named
  150. LOCATION.TXT something such as:
  151.  
  152. 5322 was found in position 532.
  153.  
  154. Only indicate the first instance of the number you encounter.
  155.  
  156. Next Time
  157. =========
  158. We will cover some basic concepts of the use of pointers.  Please
  159. write any comments you have to ggrotz@2sprint.net.  As I look at
  160. my formatted version, so far there has been 116 pages written of
  161. this tutorial, from part 1, not counting this one.  As I look through
  162. my line count figures, this one is the smallest. (interesting facts,
  163. huh?)
  164.  
  165. I will ask for feedback on how I do with regards to any of the pointer
  166. related texts coming up.  Please do that.  Thank you.
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.